模拟赛题解/2025.8.26 模拟赛

T1-运动会（sports）

题面

要将 $2n$ 个数分为两组，第 $i$ 个数的值为 $a_i$。

有 $m$ 对关系 $(x_i,y_i,b_i)$ 表示当第 $x_i$ 个数和第 $y_i$ 个数被分到同一组时，会产生额外 $b_i$ 的贡献。

求分组之后两组之间总和差的最大值是多少。

$1\leq t\leq5,1\leq n\leq10^5,1\leq m\leq2\times10^5,1\leq x_i,y_i\leq2n,1\leq a_i,b_i\leq 10^9$。

保证对 $\forall 1\leq i<j\leq m$，有 $(x_i,y_i)\not=(x_j,y_j)$ 且 $(x_i,y_i)\not=(y_j,x_j)$。

题解

$a$ 全相等，此时只需考虑朋友关系的贡献。

考虑如下贪心过程：设与 $i$ 相关的朋友关系的默契度之和为 $s_i$，则选 $s$ 从大到小排序后的前 $n$ 个人分成一组，剩下的分成另一组，答案即为 $\frac{1}{2}\left(\sum_{i=1}^ns_i-\sum_{i=n+1}^{2n}s_i\right)$。

证明：对于朋友关系 $(x,y,b)$，如果 (x,y) 在同一组，则对答案的贡献为 $2b$ 或 $-2b$。否则，贡献为 $0$，即贡献被抵消掉了。\

复杂度 $O(m+n\log n)$。

考虑每个人的力量，则将每个 $s_i$ 额外加上 $2s_i$ 然后跑上述贪心即可。

T2-卡牌（card）

题面

有 $n$ 张卡牌，每张卡牌背面有一个数字 $a_i$，正面空白。

初始全部正面朝上，可以做以下操作任意次：

• 选择一个 $i$ 满足 $1\leq i\leq m$。
• 翻转从左到右第 $l_i,\cdots,r_i$ 张牌的正反面，代价为 $w_i$。

设最后背面朝上的卡牌写着的数的总和是 $S$，所有操作的代价总和为 $T$，则最终得分为 $S-T$。

求最大可能得分。

$1\leq t\leq5,1\leq n,m\leq2\times10^5,1\leq l_i,r_i\leq n,1\leq a_i,w_i\leq10^9$。

题解

每个区间不交，对每个区间单独考虑，每个区间的贡献即为 $\max(0,\left(\sum_{i=l_i}^{r_i}a_j\right)-w_i)$。

显然每个 $l_i=1$ 和每个 $r_i=n$ 的区间都分别只会被操作其中一个。枚举翻转了 $l_i=1,r_i=x$ 这个前缀，考虑每个 $r_j=n$ 的区间。如果 $l_j>x$，则此时答案为 $\left(\sum_{k=1}^xa_k\right)+\left(\sum_{k=l_j}^na_k\right)-w_i-w_j$。

如果 $l_j\leq x$，则还需减去相交部分的和。分别维护即可。

考虑做如下转化：初始答案为 $\sum_{i=1}^na_i$。若最后无法翻转 $i$，视作花费 $a_i$ 的代价操作 $i$ 这个点。

因此，初始时先将每个 $(i,i,a_i)$ 加入操作中，即转化为操作若干次使所有卡片都被翻转的最小代价。\

我们考虑 建这样一张图：点集为 $1\sim n+1$，边为所有的 $(l_i,r_i+1,w_i)$ 和 $i,i+1,a_i$，然后求 $1$ 至 $n+1$ 的最短路即可。易证一条 $1$ 至 $n+1$ 的路径对应了一种将所有卡片翻转的操作方案。

复杂度 $O((n+m)\log(n+m))$。

T3-队形安排（formation）

题面

有 $n$ 个同学，第 $i$ 个同学的初始位置为 $x_i$，需要将每个同学的位置向左或向右移动 $d$ 个单位。

需要将同学分为若干排，设一共站成 $k$ 排，第 $i$ 排的同学的编号集合为 $S_i$，则定义凌乱程度为：

$$\sum_{i=1}^ka+b\times(\max_{j\in S_i}y_j-\min_{j\in S_i}y_j)$$

$a,b$ 为给定常数，求所有可能的队形的凌乱程度的最小值。

$1\leq t\leq5,1\leq n\leq100,1\leq d\leq30,1\leq a,b\leq10^6,1\leq x_i\leq 100$。

题解

当 $d \leq9$ 时。我们先将题意转化为要求每个人不动或向右移动 $2d$。

为了方便计算，称第 $i$ 位置被覆盖，为当前位置有人，或者存在两个位置为 $l, r(l < r)$ 的人，使得这两个人被分在同一组，且 $l \leq i \leq r$。设 $v_i$ 表示位置 $i$ 最终是否被覆盖，则答案为 $a\times\sum_iv_i+\min(0,b-a)\times\sum_i(v_i\wedge v_{i-1})$。

我们的限制形如，对于一个位置 $x$ 的人，要求最后位置 $x$ 和 $x+2d$ 中至少有一个被覆盖。

考虑状态压缩。设 $f_{i,S}$ 表示考虑到位置 $i$，前 $2d$ 个位置的覆盖情况为 $S$。设移动后最左和最右的人的位置之差为 $V$，则这样的状态总数是 $O(V \times 2^{2d})$ 的。由于 $V \leq 160$，因此状态数可以接受。

考虑如何转移。设从左到右到了 $i-1$，枚举位置 $i$ 是否被覆盖。如果存在一个人的初始位置为 $i-2d$，则需要要求 $i$ 被覆盖或者 $i-2d$ 被覆盖，这是容易判断的。贡献直接按照上述式子计算即可。复杂度 $O(t \times V \times 2^{2d})$。

考虑 $d$ 较大的情况。修改一下状态，设 $f_{i,S}$ 表示位置 $i, 2d+1, 4d+1, \dots$ 的覆盖情况为 $S$ 从 $i$ 转移到 $i+1$。所需要的判断和贡献计算都是类似的。此外，我们需要额外记录下 $1, 2d+1, 4d+1, \dots$ 的状态，以便在计算完后计算 $2d, 4d, 6d, \dots$ 和 $1, 2d+1, 4d+1, \dots$ 之间产生的贡献。

这个算法的复杂度为 $O(V \times 2^{V/d})$，在 $d > 9$ 时可以接受。于是我们在 $d \leq 9$ 时运行上一个算法，在 $d > 9$ 时运行该算法，即可通过所有数据。

T4-二零四八（game）

题面

有一棵 n 个结点的树，初始 $i$ 号结点上有一个数 $2^{a_i}$。

一轮游戏的过程如下：

• 每次可以选择一条边，满足这条边两个端点上的数相等。然后，把这条边缩成一个新点，新点上的数为两个端点上的数之和。
• 如果在重复执行以上操作后，能使树上仅剩一个结点，那么你将获得游戏的胜利。

将进行 $q$ 轮游戏。每轮游戏开始前，会交换某条边两个端点上写着的数。

对于每轮游戏，你想知道是否存在一种方案使你能获胜。注意，每轮游戏之间是独立的，但是修改是永久的。

$1\leq n,q\leq2\times10^5,1\leq a_i\leq n,1\leq x_i,y_i\leq n$。

题解

$m \leq 10$ 时，按值从小到大操作，发现合法的充要条件是，对于当前操作到的值 $v$，所有点值为 $2^v$ 的点的导出子图有完美匹配。于是从小到大模拟收缩的过程。

带修改，我们需要一个更好的判定合法的方式，即需要快速对每个操作到的 $v$，判定其导出子图是否有完美匹配。

这里给出一个结论：假设一个有根树的某些点被染为黑色，其余点为白色。记黑点总数为 $s$，子树内有奇数个黑点的子树个数记为 $t$。此时有 $\left\lfloor \frac{s}{2} \right\rfloor \leq t$。

等号是否成立即为黑点导出子图是否有完美匹配的充要条件。

严格证明可以使用归纳法。感性理解：对于一个黑点 $x$ 满足它的子树黑点数为奇数，那么 $x$ 的父亲必须为黑点。所以这样的子树必须有 $s/2$ 个。

于是我们可以把这个问题拆为两个子问题：对于所有 $v$，求操作到 $v$ 时点值为 $2^v$ 的点的个数，以及求此时有多少个子树内部点数为奇数个 $2^v$。

对于第一个子问题，由于修改并未改变数值性质，所以可以在询问前预处理。

对于第二个子问题，我们考虑计算出每个子树的点值之和 $S$，那么这个子树在操作到 $2^v = \text{lowbit}(S)$ 时做贡献。可以用 set 启发式合并维护二进制位，进位数量 $O(n)$ 的，可以直接维护。

对于修改，我们发现只会影响这条边深度较大的那个点的子树内，修改形如减去一个 $2^i$ 再加一个 $2^j$。我们把操作拆到在这个点上，在 set 里维护 $+1$ 的连续段，即可做到 $O(\log n)$ 加减一个二进制位。

总复杂度 $O(n \log^2 n + m \log n)$。